//
//  main.c
//  顺序栈1
//
//  Created by Song on 2018/3/7.
//  Copyright © 2018年 Song. All rights reserved.
//

// *S.top++=e ： 先算 *S.top=e; 再 S.top++;

//  顺序栈

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *base; // 栈底指针
    int *top; // 栈顶指针
    int stacksize; // 栈的容量，能装多少个元素（并不是当前栈中元素数量）
}SqStack;

// 1.初始化栈
void initStack(SqStack *stack) {
    stack->base = (int *)malloc(sizeof(int));
    if (!stack) {return;}
    stack->top = stack->base;
    stack->stacksize = 100; // ?
}

// 2.销毁栈
void distroyStack(SqStack *s) {
    s->top = NULL;
    s->stacksize = 0;
    free(s->base);
    printf("栈已被销毁\n");
}

// 3.压栈
void push(SqStack *stack, int elem) {
    
    if (stack->top - stack->base >= stack->stacksize) { // 如果栈满了,就扩容
        stack->base = (int *)realloc(stack->base, (stack->stacksize + 10) *sizeof(int)); // 10 代表增量
        if (!stack->base) {return;}
        
        // 可能得到的空间，是重新分配的（基地址会变），也可能是在原来的基础扩充
        // 这条语句可以在重新分配空间的情况下，正确得到栈顶指针的位置
        stack->top = stack->base + stack->stacksize;
        
        stack->stacksize += 10;
    }
//    stack->top ++; // 栈顶指针 +1
    *stack->top  = elem; // 将新元素赋值给栈顶空间
    stack->top ++; // 栈顶指针 +1
}

// 4.出栈
int pop(SqStack *s,int *e) {
    if (s->top == s->base) {
        printf("栈为空\n");
        return 0; // 栈为空
    } else {
        s->top--; // s->top 指向的是最上方元素的上面的空位，所以要减一（压栈的时候栈顶指针+1了）
        e = s->top; // 实际上此元素并没真正删除，仍在S.top中，但是如果插入元素，就会被更新，就像是删除了一样
        
        return *e;
    }
}

// test 输出 s->base
int test(SqStack *s) {
    int test;
//    s->base = s->base - 1; // 真正的栈底
    test = *s->base;
    return test;
}

// 5.清空栈
void clearStack(SqStack *s) {
    s->top = s->base;
}

// 6.求栈长
long lengthStack(SqStack *s) {
    if (s->top == s->base) {
        return 0;
    }else {
        return (s->top - s->base);
    }
}

// 7.遍历栈 并输出
void stackPrint(SqStack *s) {
    if (s->base == NULL) {
        printf(" = s->base == NULL \n");
        return;
    }
    if (s->top == s->base) {
        printf(" = 栈中没有元素\n");
        return;
    }
    int *p;
    p = s->top; // p 指向栈顶指针
    printf("栈中元素为：");
    while (p > s->base) {
        p--; // （压栈的时候栈顶指针+1了）先减一，后输出
        printf("%d ",*p);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    SqStack stack;
    initStack(&stack); // 初始化栈
    
    stackPrint(&stack); // 输出栈（空的）
    
    int element; // 入栈元素
    int num = 0; // 入栈元素个数
    long l; // 栈长
    printf("输入想要入栈的元素个数：\n");
    scanf("%d",&num);
    for (int i = 0; i < num; i++) {
        printf("输入想要入栈的第%d元素：",i+1);
        scanf("%d",&element);
        push(&stack, element); // 压入栈
    }
    stackPrint(&stack); // 遍历输出栈中的元素，自栈顶向下
    
    l = lengthStack(&stack);
    printf("栈长为：%ld\n",l);
    
    int e = 0;
    e = pop(&stack, &e); // 删除栈顶元素 出栈
    printf("pop了栈顶元素： %d \n",e);
    stackPrint(&stack); // 输出 出栈后的栈内元素
    
    
    l = lengthStack(&stack);
    printf("栈长为：%ld\n",l);
    
    clearStack(&stack);
    l = lengthStack(&stack);
    printf("清空栈后，栈长为：%ld\n",l);
    
//    int test1;
//    test1 = test(&stack);
//    printf(" ======================= %d\n",test1);
//
//    clearStack(&stack); // 清空了栈
//    test1 = test(&stack);
//    printf(" ======================= %d\n",test1);
//    stackPrint(&stack);
    
    distroyStack(&stack); // 销毁栈
    return 0;
}


















